import numpy as np
file_path = 'Data.txt'
out_path = 'block_result.txt'

# 打开并读取文件
with open(file_path, 'r') as f:
    lines = f.readlines()

# 初始化两个空列表
from_nodes = []
to_nodes = []
degree = []
max_node_id = 0
max_to_id = 0

matrixs = {}
group_nodes = 100

# 遍历每一行
for line in lines:
    # 分割行并将结果添加到列表中
    from_node_id, to_node_id = map(int, line.split())

    group = (to_node_id - 1) // group_nodes #计算出所属的组 

    if group not in matrixs:  #如果matrixs中没有这个组，就创建一个
        matrixs[group] = {}
        matrixs[group][from_node_id - 1] = [to_node_id - 1]
    else:
        if from_node_id - 1 not in matrixs[group]: #如果这个组中没有这个节点，创建该节点
            matrixs[group][from_node_id - 1] = [to_node_id - 1]
        else:
            matrixs[group][from_node_id - 1].append(to_node_id - 1) #如果这个组中有这个节点，添加到该节点的列表中

    if(from_node_id > max_node_id):
        for i in range(max_node_id, from_node_id ):
            degree.append(0)
        max_node_id = from_node_id
    
    if(to_node_id > max_to_id):
        max_to_id = to_node_id
        
    degree[from_node_id - 1] += 1 #计算出度

    from_nodes.append(from_node_id - 1)
    to_nodes.append(to_node_id - 1)

node_nums = max(max_node_id, max_to_id) 
group_nums = node_nums // group_nodes + 1 #计算组数
degree = np.array(degree)
dead_ends = np.where(degree == 0)[0]    #找出度为0的节点


rank_old = np.ones(node_nums) / node_nums
d = 0.85
epsilon = 1e-8

while True:
    rank_new = np.ones(node_nums) * (1 - d) / node_nums

    rank_new += d * np.sum(rank_old[dead_ends]) / node_nums  #先处理所有dead_end节点

    for group, matrix in matrixs.items():   #对每个分块矩阵进行迭代计算
        group_start = group * group_nodes
        group_end = (group + 1) * group_nodes  if (group + 1) * group_nodes < node_nums else node_nums

        for from_node, to_nodes in matrix.items():  #该分块矩阵中的每一列
            for to_node in to_nodes:
                rank_new[to_node] += d * rank_old[from_node] / degree[from_node] #更新rank值
                     
    diff = np.sum(np.abs(rank_new - rank_old))
    if diff < node_nums * epsilon:
        break
    
    rank_old = rank_new
    

top_indices = np.argsort(rank_new)[::-1][:100] #找出前100个最大值的索引
top_values = rank_new[top_indices]

for i in range(100):
    print(f"Index: {top_indices[i] + 1}, Value: {top_values[i]}")

with open(out_path, 'w') as f:
    for i in range(100):
        f.write(f"{top_indices[i] + 1} {top_values[i]}\n")


